package Sort;

import org.junit.Test;

/**
 * @author yyq
 * @create 2021-10-16 13:18
 * 快速排序
 */
public class QuickSort {
    public void quickSort(int a[],int low,int high){
        if (low<high){                        //快排结束
            int location = sort(a, low, high);//分割  比loc小 location 比loc大
            quickSort(a,low,location-1); //对左边继续快排
            quickSort(a,location+1,high);//对右边继续快排
        }


    }

    private int sort(int[] a, int low, int high) {
        int temp=a[low];
        while(low<high){
            while(a[high]>=temp) {
                if(high>low)
                high--;
                else break;
            }

            if(a[high]<temp){
                a[low]=a[high];
            }
            while (a[low]<=temp){
                if(low<high)
                low++;
                else break;
            }
            if(a[low]>temp){
                a[high]=a[low];
            }
        }
        a[low]=temp;
        return low;
    }
    @Test
    public void test(){
        int[] a={213,2,3,2,4,5,6,7,8,21,3};
        quickSort(a,0,a.length-1);
        for (int i : a) {
            System.out.println(i);
        }
    }

}
